package concurrent.sort;

import org.junit.Test;

import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

/**
 * 奇偶交换排序，源自冒泡
 * 分两个阶段
 * 1.奇阶段 总是比较奇数索引及其相连的后续元素
 * 2.偶阶段 总是比较偶数索引及其相连的后续元素
 */
public class OddEvenSort {

    static int[] arr = {1,2,3,41,54,12,4,7};

    @Test
    public void oddEvenSort() {
        System.out.println("排序前： " + display(arr));
        int exchFlag = 1, start = 0;
        while (exchFlag ==1 || start == 1) {
            exchFlag = 0;
            for (int i=start; i<arr.length - 1; i+=2) {
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    exchFlag = 1;
                }
            }
            if (start == 0)
                start = 1;
            else
                start = 0;
        }
        System.out.println("排序后： " + display(arr));
    }

    static int exchFlag = 1;
    ExecutorService pool = Executors.newCachedThreadPool();
    static synchronized void setExchFlag(int v) {
        exchFlag = v;
    }

    static synchronized int getExchFlag() {
        return exchFlag;
    }

    static class OddEvenSortTask implements Runnable {
        int i = 0;
        CountDownLatch countDownLatch;

        public OddEvenSortTask(int i, CountDownLatch countDownLatch) {
            this.i = i;
            this.countDownLatch = countDownLatch;
        }

        @Override
        public void run() {
            if (arr[i] > arr[i+1]){
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
                setExchFlag(1);
            }
            countDownLatch.countDown();
        }
    }


    @Test
    public void pOddEvenSort() throws InterruptedException {
        System.out.println("排序前： " + display(arr));
        int start = 0;
        while (getExchFlag() == 1 || start == 1) {
            setExchFlag(0);
            CountDownLatch count = new CountDownLatch(arr.length/2 - (arr.length %2==0?start:0));
            for (int i=0; i<arr.length; i+=2) {
                pool.submit(new OddEvenSortTask(i, count));
            }
            count.await();
            if (start == 0)
                start = 1;
            else
                start = 0;
        }
        Thread.sleep(2000);
        System.out.println("排序后： " + display(arr));
    }

    private String display(int[] arr) {
        String s = "";
        for (int a:arr) {
            s += a + ",";
        }
        return s;
    }

}
